#include <ut/UnitTest.h>
#include <illib/Log.h>
#include <illib/System.h>
#include <illib/RedBlackTree.h>
#include <illib/Exception.h>
#include <limits>

using namespace illib;

namespace illib_ut{
	template<class T> class SingleTestTreeFunctions : public RedBlackTree::Functions<T> {
	public:
		virtual bool lesser(RedBlackTree::Node<T> &left, RedBlackTree::Node<T> &right){
			bool result = (left.number_ < right.number_);
			return result;
		}
		virtual bool greater(RedBlackTree::Node<T> &left, RedBlackTree::Node<T> &right){
			bool result = (left.number_ > right.number_);
			return result;
		}
		virtual bool equal(RedBlackTree::Node<T> &left, RedBlackTree::Node<T> &right){
			bool result = (left.number_ == right.number_);
			return result;
		}
	};
	class UInt8{
	public:
		uint8_t number_;
		UInt8(){}
		UInt8(uint8_t number) :
			number_(number)
		{

		}
		static uint8_t max(){
			return std::numeric_limits<uint8_t>::max();
		}
	};
	class UInt64{
	public:
		uint64_t number_;
		UInt64(){}
		UInt64(uint64_t number) :
			number_(number)
		{

		}
		static uint64_t max(){
			return std::numeric_limits<uint64_t>::max();
		}
	};
	class Range {
	public:
		void set(uint32_t start, uint32_t size)
		{
			start_ = start;
			size_ = size;
			end_ = start_+size_;
		}
		Range() :
			start_(0),
			size_(0)
		{

		}
		uint32_t start_;
		uint32_t size_;
		uint32_t end_;
	};
	class RangeTestTreeFunctions : public RedBlackTree::Functions<Range> {
	public:
		virtual bool lesser(RedBlackTree::Node<Range> &left, RedBlackTree::Node<Range> &right){
			bool result = ((left.start_ < right.start_) && (left.end_ < right.end_));
			return result;
		}
		virtual bool greater(RedBlackTree::Node<Range> &left, RedBlackTree::Node<Range> &right){
			bool result = (left.start_ > right.end_);
			return result;
		}
		virtual bool equal(RedBlackTree::Node<Range> &left, RedBlackTree::Node<Range> &right){
			bool result = ((left.start_ >= right.start_) && (left.end_ <= right.end_));
			return result;
		}
	};

	template<class T> void testRedBlackTree(RedBlackTree::Tree<T> &tree, SingleTestTreeFunctions<T> &functions, Allocator &allocator){

		/*const size_t count1 = 200;
		SingleTestNode nodes1[count1];
		for(uint32_t i = 0; i < count1; i++){
			nodes1[i].number_ = i*20+400;
			tree.add(nodes1[i]);
		}*/

		RedBlackTree::Node<T> &m5 = RedBlackTree::Node<T>::create(allocator, sizeof(RedBlackTree::Node<T>));
		m5.number_ = 10;
		tree.add(m5, functions);
		RedBlackTree::Node<T> &m1 = RedBlackTree::Node<T>::create(allocator, sizeof(RedBlackTree::Node<T>));
		m1.number_ = 20;
		tree.add(m1, functions);
		RedBlackTree::Node<T> &m2 = RedBlackTree::Node<T>::create(allocator, sizeof(RedBlackTree::Node<T>));
		m2.number_ = 40;
		tree.add(m2, functions);
		RedBlackTree::Node<T> &m6 = RedBlackTree::Node<T>::create(allocator, sizeof(RedBlackTree::Node<T>));
		m6.number_ = 120;
		tree.add(m6, functions);
		RedBlackTree::Node<T> &m3 = RedBlackTree::Node<T>::create(allocator, sizeof(RedBlackTree::Node<T>));
		m3.number_ = 60;
		tree.add(m3, functions);
		RedBlackTree::Node<T> &m4 = RedBlackTree::Node<T>::create(allocator, sizeof(RedBlackTree::Node<T>));
		m4.number_ = 80;
		tree.add(m4, functions);
/*
		const size_t count2 = 100;
		SingleTestNode nodes2[count2];
		for(uint32_t i = 0; i < count2; i++){
			nodes2[i].number_ = i+101;
			tree.add(nodes2[i]);
		}
*/
		{
			//Console::print("find positive forward 80\n");
			RedBlackTree::Node<T> f;
			f.number_ = 80;
			RedBlackTree::Iterator<T> i(f, tree, functions, true);
			ut::test(AT(), EX(i.current() != 0), TN(RedBlackTree::Iterator::current));
			ut::test(AT(), EX(i.current()->number_ == f.number_), TN(RedBlackTree::Iterator::current));
		}

		{
			//Console::print("find positive reverse 80\n");
			RedBlackTree::Node<T> f;
			f.number_ = 80;
			RedBlackTree::Iterator<T> i(f, tree, functions, false);
			ut::test(AT(), EX(i.current() != 0), TN(RedBlackTree::Iterator::current));
			ut::test(AT(), EX(i.current()->number_ == f.number_), TN(RedBlackTree::Iterator::current));
		}

		{
			//Console::print("find negative forward 70\n");
			RedBlackTree::Node<T> f;
			f.number_ = 70;
			RedBlackTree::Iterator<T> i(f, tree, functions, true);
			ut::test(AT(), EX(i.current() == 0), TN(RedBlackTree::Iterator::current));
		}

		{
			//Console::print("find negative reverse 70\n");
			RedBlackTree::Node<T> f;
			f.number_ = 70;
			RedBlackTree::Iterator<T> i(f, tree, functions, false);
			ut::test(AT(), EX(i.current() == 0), TN(RedBlackTree::Iterator::current));
		}

		{
			//Console::print("iterate forward\n");
			RedBlackTree::Iterator<T> i(tree, functions, true);
			T n(0);
			ut::test(AT(), EX(i.current() != 0), TN(RedBlackTree::Iterator::current));
			while(i.current()){
				ut::test(AT(), EX(i.current()->number_ > n.number_), TN(RedBlackTree::Iterator::current));
				n.number_ = i.current()->number_;
				i.next();
			}
		}

		{
			//Console::print("iterate reverse\n");
			RedBlackTree::Iterator<T> i(tree, functions, false);
			ut::test(AT(), EX(i.current() != 0), TN(RedBlackTree::Iterator::current));
			T n(T::max());
			while(i.current()){
				ut::test(AT(), EX(i.current()->number_ < n.number_), TN(RedBlackTree::Iterator::current));
				n.number_ = i.current()->number_;
				i.next();
			}
		}

		{
			//Console::print("find positive forward 50\n");
			RedBlackTree::Node<T> s;
			s.number_ = 50;
			RedBlackTree::Node<T> e;
			e.number_ = 100;
			RedBlackTree::Iterator<T> i(s, e, tree, functions, true);
			ut::test(AT(), EX(i.current() != 0), TN(RedBlackTree::Iterator::current));
			T n(0);
			while(i.current()){
				ut::test(AT(), EX(i.current()->number_ > s.number_), TN(RedBlackTree::Iterator::current));
				ut::test(AT(), EX(i.current()->number_ <= e.number_), TN(RedBlackTree::Iterator::current));
				ut::test(AT(), EX(i.current()->number_ > n.number_), TN(BasicRedBlackTree::Iterator::current));
				n.number_ = i.current()->number_;
				i.next();
			}
		}

		{
			//Console::print("find positive reverse 50\n");
			RedBlackTree::Node<T> s;
			s.number_ = 50;
			RedBlackTree::Node<T> e;
			e.number_ = 100;
			RedBlackTree::Iterator<T> i(s, e, tree, functions, false);
			ut::test(AT(), EX(i.current() != 0), TN(RedBlackTree::Iterator::current));
			T n(T::max());
			while(i.current()){
				ut::test(AT(), EX(i.current()->number_ > s.number_), TN(RedBlackTree::Iterator::current));
				ut::test(AT(), EX(i.current()->number_ <= e.number_), TN(RedBlackTree::Iterator::current));
				ut::test(AT(), EX(i.current()->number_ < n.number_), TN(BasicRedBlackTree::Iterator::current));
				n.number_ = i.current()->number_;
				i.next();
			}
		}
	}

	void testRangeRedBlackTree(RedBlackTree::Tree<Range> &tree, RangeTestTreeFunctions &functions, Allocator &allocator) {
		{

			/*const size_t count1 = 200;
			RangeTestNode nodes1[count1];
			for(uint32_t i = 0; i < count1; i++){
				nodes1[i].start_ = (i*20)+400;
				nodes1[i].size_ = 10;
				tree.add(nodes1[i], functions);
			}*/

			RedBlackTree::Node<Range> &m5 = RedBlackTree::Node<Range>::create(allocator, sizeof(RedBlackTree::Node<Range>));
			m5.set(100,10);
			tree.add(m5, functions);
			RedBlackTree::Node<Range> &m1 = RedBlackTree::Node<Range>::create(allocator, sizeof(RedBlackTree::Node<Range>));
			m1.set(20,10);
			tree.add(m1, functions);
			RedBlackTree::Node<Range> &m2 = RedBlackTree::Node<Range>::create(allocator, sizeof(RedBlackTree::Node<Range>));
			m2.set(40,10);
			tree.add(m2, functions);
			RedBlackTree::Node<Range> &m6 = RedBlackTree::Node<Range>::create(allocator, sizeof(RedBlackTree::Node<Range>));
			m6.set(120,10);
			tree.add(m6, functions);
			RedBlackTree::Node<Range> &m3 = RedBlackTree::Node<Range>::create(allocator, sizeof(RedBlackTree::Node<Range>));
			m3.set(60,10);
			tree.add(m3, functions);
			RedBlackTree::Node<Range> &m4 = RedBlackTree::Node<Range>::create(allocator, sizeof(RedBlackTree::Node<Range>));
			m4.set(80,10);
			tree.add(m4, functions);

			/*const size_t count2 = 100;
			RangeTestNode nodes2[count2];
			for(uint32_t i = 0; i < count2; i++){
				nodes2[i].start_ = (i*10)+101;
				nodes2[i].size_ = 5;
				tree.add(nodes2[i], functions);
			}*/
			{
				//Console::print("find positive forward range 85\n");
				RedBlackTree::Node<Range> f;
				f.set(85,0);
				RedBlackTree::Iterator<Range> i(f, tree, functions, true);
				ut::test(AT(), EX(i.current() != 0), TN(RedBlackTree::Iterator::current));
			}
			{
				//Console::print("find positive reverse range 85\n");
				RedBlackTree::Node<Range> f;
				f.set(85,0);
				RedBlackTree::Iterator<Range> i(f, tree, functions, false);
				ut::test(AT(), EX(i.current() != 0), TN(RedBlackTree::Iterator::current));
			}
		}
	};

	void RedBlackTree_ut(){
		ut::UnitTestLogger logger(TN(illib_ut::RedBlackTree_ut));
		{
			SingleTestTreeFunctions<UInt8> functions;
			PoolAllocator::BasicAllocator allocator(
					System::align<RedBlackTree::Node<UInt8> >(),
					System::allocator().pagesize(), alignof(RedBlackTree::Node<UInt8>), 0);
			RedBlackTree::Tree<UInt8> tree;
			testRedBlackTree(tree, functions, allocator);
			tree.clear(&allocator, functions);
		}
		{
			SingleTestTreeFunctions<UInt64> functions;
			PoolAllocator::BasicAllocator allocator(
					System::align<RedBlackTree::Node<UInt64> >(),
					System::allocator().pagesize(), alignof(RedBlackTree::Node<UInt64>), 0);
			RedBlackTree::Tree<UInt64> tree;
			testRedBlackTree(tree, functions, allocator);
			tree.clear(&allocator, functions);
		}
		{
			RangeTestTreeFunctions functions;
			PoolAllocator::BasicAllocator allocator(
					System::align<RedBlackTree::Node<Range> >(),
					System::allocator().pagesize(), alignof(RedBlackTree::Node<Range>), 0);
			RedBlackTree::Tree<Range> tree;
			testRangeRedBlackTree(tree, functions, allocator);
			tree.clear(&allocator, functions);
		}
	}
};
